Definition

𝐏𝐒𝐏𝐀𝐂𝐄\mathbf{PSPACE} represents decision problems decidable in polynomial amounts of space, i.e.

𝐏𝐒𝐏𝐀𝐂𝐄=∪c>0𝐒𝐏𝐀𝐂𝐄(nc)\mathbf{PSPACE} = \cup_{c > 0} \mathbf{SPACE}(n^c)

(SPACE)

Proposition

P ⊆\subseteq NP ⊆\subseteq PH ⊆𝐏𝐒𝐏𝐀𝐂𝐄=\subseteq \mathbf{PSPACE} = NPSPACE ⊆\subseteq EXPTIME

Notes

  • PSPACE and NSPACE can be thought of as the space analogs of time complexity classes P and NP respectively

See also

References

  1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 81.
  2. https://home.csulb.edu/~tebert/teaching/lectures/419-519/pspace/pspace.pdf
  3. https://webdocs.cs.ualberta.ca/~zacharyf/courses/complexity_2019/notes/complexity-w19-lec03.pdf
  4. https://mathoverflow.net/questions/39690/how-is-p-related-to-other-complexity-classes